﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DirectedGraphCycle
{
    class FindAllDirectedCycle : FindAllCycle
    {
        public FindAllDirectedCycle()
        {
        }

        public override ArrayList getAllCycles()
        {
            this.cycles = new ArrayList();
            this.blocked = new bool[this.numNodes];
            this.B = new ArrayList[this.numNodes];
            this.stack = new ArrayList();
            StrongConnectedComponents sccs = new StrongConnectedComponents(this.adjacencyListOriginal);
            int s = 0;

            while (true)
            {
                SCCResult sccResult = sccs.getStrongConnectedComponent(s);
                if (sccResult != null && sccResult.getAdjList() != null)
                {
                    ArrayList[] scc = sccResult.getAdjList();
                    s = sccResult.getLowestNodeId();
                    for (int j = 0; j < scc.Length; j++)
                    {
                        if ((scc[j] != null) && (scc[j].Count > 0))
                        {
                            this.blocked[j] = false;
                            this.B[j] = new ArrayList();
                        }
                    }

                    this.circuit(s, s, scc);
                    s++;
                }
                else
                {
                    break;
                }
            }

            return this.cycles;
        }

        private bool circuit(int v, int s, ArrayList[] adjListGraph)
        {
            bool f = false;
            this.stack.Add(v);
            this.blocked[v] = true;

            for (int i = 0; i < adjListGraph[v].Count; i++)
            {
                int w = (int)adjListGraph[v][i];

                if (w == s)
                {
                    ArrayList cycle = new ArrayList();
                    for (int j = 0; j < stack.Count; j++)
                    {
                        cycle.Add(stack[j]);
                    }
                    this.cycles.Add(cycle);
                    f = true;
                }
                else if (!this.blocked[w])
                {
                    if (this.circuit(w, s, adjListGraph))
                    {
                        f = true;
                    }
                }
            }

            if (f)
            {
                this.unblock(v);
            }
            else
            {
                for (int i = 0; i < adjListGraph[v].Count; i++)
                {
                    int w = (int)adjListGraph[v][i];
                    if (!this.B[w].Contains(v))
                    {
                        this.B[w].Add(v);
                    }
                }
            }

            this.stack.Remove(v);

            return f;
        }

        private void unblock(int u)
        {
            this.blocked[u] = false;
            while (B[u].Count > 0)
            {
                int w = (int)B[u][0];
                B[u].RemoveAt(0);
                if (this.blocked[w])
                {
                    this.unblock(w);
                }
            }
        }
    }
}
